package vip.george.p0054;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class P54 {


    /**
     * 方法1:
     * 按圈遍历，逐层缩小，按照每圈来遍历(需要考虑单行和单列的情况)
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return list;
        }

        int width = matrix[0].length;
        int height = matrix.length;

        //每次遍历一圈的起始坐标位置
        int x = 0, y = 0;
        //每次遍历一圈
        while (width > 0 && height > 0) {
//            System.out.println("当前的圈：" + width + " " + height);
            //上面一行
            for (int i = 0; i < width; i++) {
                list.add(matrix[x][y + i]);
            }
            // 右边一列
            for (int i = 1; i < height; i++) {
                list.add(matrix[x + i][y + width - 1]);
            }
            //只有宽高都大于1的时候才遍历 下面的行和左边的列
            if (width > 1 && height > 1) {
                //下面一行
                for (int i = width - 2; i >= 0; i--) {
                    list.add(matrix[x + height - 1][y + i]);
                }
                //左边一列
                for (int i = height - 2; i >= 1; i--) {
                    list.add(matrix[x + i][y]);
                }
            }
            //每次遍历完一圈长宽就都减2
            width -= 2;
            height -= 2;
            // 更新起始坐标位置
            x += 1;
            y += 1;
        }
        return list;
    }


    /**
     * 方法2:
     * 四边界控制，每遍历一个边，这个边的边界就收缩，直到出现边界交叉的时候才停止遍历
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder2(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int top = 0, right = matrix[0].length - 1, bottom = matrix.length - 1, left = 0;
        while (top <= bottom && left <= right) {
            // 上
            for (int i = left; i <= right; i++) {
                list.add(matrix[top][i]);
            }
            top++;
            if (top > bottom) {
                break;
            }

            // 右
            for (int i = top; i <= bottom; i++) {
                list.add(matrix[i][right]);
            }
            right--;
            if (left > right) {
                break;
            }

            // 下
            for (int i = right; i >=left ; i--) {
                list.add(matrix[bottom][i]);
            }
            bottom--;
            if (top > bottom) {
                break;
            }

            // 左
            for (int i = bottom; i >= top; i--) {
                list.add(matrix[i][left]);
            }
            left++;
            if (left > right) {
                break;
            }
        }
        return list;
    }


    public static void main(String[] args) {
        P54 p54 = new P54();
        System.out.println("=========方法1：===========");
        System.out.println(p54.spiralOrder(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}));
        System.out.println(p54.spiralOrder(new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}));
        System.out.println(p54.spiralOrder(new int[][]{{1, 2}}));
        System.out.println(p54.spiralOrder(new int[][]{{1}, {2}, {3}}));
        System.out.println("==========方法2：==========");
        System.out.println(p54.spiralOrder2(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}));
        System.out.println(p54.spiralOrder2(new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}));
        System.out.println(p54.spiralOrder2(new int[][]{{1, 2}}));
        System.out.println(p54.spiralOrder2(new int[][]{{1}, {2}, {3}}));
    }
}
